      1  import java.util.NoSuchElementException;

      2

      3  /**

      4     This program tests the doubly linked list implementation.

      5  */

      6  public class LinkedListTest

      7  {

      8     public static void main(String[] args)

      9     {

     10        LinkedList lst = new LinkedList();

     11        check("", lst, "Constructing empty list");

     12        lst.addLast("A");

     13        check("A", lst, "Adding last to empty list");

     14        lst.addLast("B");

     15        check("AB", lst, "Adding last to non-empty list");

     16

     17        lst = new LinkedList();

     18        lst.addFirst("A");

     19        check("A", lst, "Adding first to empty list");

     20        lst.addFirst("B");

     21        check("BA", lst, "Adding first to non-empty list");

     22

     23        assertEquals("B", lst.removeFirst());

     24        check("A", lst, "Removing first, yielding non-empty list");

     25        assertEquals("A", lst.removeFirst());

     26        check("", lst, "Removing first, yielding empty list");

     27

     28        lst = new LinkedList();

     29        lst.addLast("A");

     30        lst.addLast("B");

     31        check("AB", lst, "");

     32

     33        assertEquals("B", lst.removeLast());

     34        check("A", lst, "Removing last, yielding non-empty list");

     35        assertEquals("A", lst.removeLast());

     36        check("", lst, "Removing last, yielding empty list");

     37

     38        lst = new LinkedList();

     39        lst.addLast("A");

     40        lst.addLast("B");

     41        lst.addLast("C");

     42        check("ABC", lst, "");

     43

     44        ListIterator iter = lst.listIterator();

     45        assertEquals("A", iter.next());

     46        iter.set("D");

     47        check("DBC", lst, "Set element after next");

     48        assertEquals("D", iter.previous());

     49        iter.set("E");

     50        check("EBC", lst, "Set first element after previous");

     51        assertEquals("E", iter.next());

     52        assertEquals("B", iter.next());

     53        assertEquals("B", iter.previous());

     54        iter.set("F");

     55        check("EFC", lst, "Set second element after previous");

     56        assertEquals("F", iter.next());

     57        assertEquals("C", iter.next());

     58        assertEquals("C", iter.previous());

     59        iter.set("G");

     60        check("EFG", lst, "Set last element after previous");

     61

     62        lst = new LinkedList();

     63        lst.addLast("A");

     64        lst.addLast("B");

     65        lst.addLast("C");

     66        lst.addLast("D");

     67        lst.addLast("E");

     68        check("ABCDE", lst, "");

     69        iter = lst.listIterator();

     70        assertEquals("A", iter.next());

     71        iter.remove();

     72        check("BCDE", lst, "Remove first element after next");

     73        assertEquals("B", iter.next());

     74        assertEquals("C", iter.next());

     75        iter.remove();

     76        check("BDE", lst, "Remove middle element after next");

     77        assertEquals("D", iter.next());

     78        assertEquals("E", iter.next());

     79        iter.remove();

     80        check("BD", lst, "Remove last element after next");

     81

     82        lst = new LinkedList();

     83        lst.addLast("A");

     84        lst.addLast("B");

     85        lst.addLast("C");

     86        lst.addLast("D");

     87        lst.addLast("E");

     88        check("ABCDE", lst, "");

     89        iter = lst.listIterator();

     90        assertEquals("A", iter.next());

     91        assertEquals("B", iter.next());

     92        assertEquals("C", iter.next());

     93        assertEquals("D", iter.next());

     94        assertEquals("E", iter.next());

     95        assertEquals("E", iter.previous());

     96        iter.remove();

     97        check("ABCD", lst, "Remove last element after previous");

     98        assertEquals("D", iter.previous());

     99        assertEquals("C", iter.previous());

    100        iter.remove();

    101        check("ABD", lst, "Remove middle element after previous");

    102        assertEquals("B", iter.previous());

    103        assertEquals("A", iter.previous());

    104        iter.remove();

    105        check("BD", lst, "Remove first element after previous");

    106

    107        lst = new LinkedList();

    108        lst.addLast("B");

    109        lst.addLast("C");

    110        check("BC", lst, "");

    111        iter = lst.listIterator();

    112        iter.add("A");

    113        check("ABC", lst, "Add first element");

    114        assertEquals("B", iter.next());

    115        iter.add("D");

    116        check("ABDC", lst, "Add middle element");

    117        assertEquals("C", iter.next());

    118        iter.add("E");

    119        check("ABDCE", lst, "Add last element");

    120     }

    121

    122     /**

    123        Checks whether two objects are equal and throws an exception if not.

    124        @param expected the expected value

    125        @param actual the actual value

    126     */

    127     public static void assertEquals(Object expected, Object actual)

    128     {

    129        if (expected == null && actual != null ||

    130           !expected.equals(actual))

    131        {

    132           throw new AssertionError("Expected " + expected + " but found " + actual);

    133        }

    134     }

    135

    136     /**

    137        Checks whether a linked list has the expected contents, and throws

    138        an exception if not.

    139        @param expected the letters that are expected in each node

    140        @param actual the linked list

    141        @param what a string explaining what has been tested. It is

    142        included in the message that is displayed when the test passes.

    143     */

    144     public static void check(String expected, LinkedList actual, String what)

    145     {

    146        int n = expected.length();

    147        if (n > 0)

    148        {

    149           // Check first and last reference

    150           assertEquals(expected.substring(0, 1), actual.getFirst());

    151           assertEquals(expected.substring(n - 1), actual.getLast());

    152

    153           // Check next references

    154           ListIterator iter = actual.listIterator();

    155           for (int i = 0; i < n; i++)

    156           {

    157              assertEquals(true, iter.hasNext());

    158              assertEquals(expected.substring(i, i + 1), iter.next());

    159           }

    160           assertEquals(false, iter.hasNext());

    161

    162           // Check previous references

    163           for (int i = n - 1 ; i >= 0; i--)

    164           {

    165              assertEquals(true, iter.hasPrevious());

    166              assertEquals(expected.substring(i, i + 1), iter.previous());

    167           }

    168           assertEquals(false, iter.hasPrevious());

    169        }

    170        else

    171        {

    172           // Check that first and last are null

    173           try

    174           {

    175              actual.getFirst();

    176              throw new IllegalStateException("first not null");

    177           }

    178           catch (NoSuchElementException ex)

    179           {

    180           }

    181

    182           try

    183           {

    184              actual.getLast();

    185              throw new IllegalStateException("last not null");

    186           }

    187           catch (NoSuchElementException ex)

    188           {

    189           }

    190        }

    191        if (what.length() > 0)

    192        {

    193           System.out.println("Passed \"" + what + "\".");

    194        }

    195     }

    196  }